// 给定一个链表的头节点head，删除链表的倒数第n个节点，并返回链表的头节点

// 思路，快慢指针，因为是删除，所以需要找到倒数第N个节点的前一个，快指针先走n步，然后快慢指针同步走，直到快指针指向空
// 时间复杂度：O(n)
// 空间复杂度：O(1)

const { LinkedList, ListNode} = require('./64.设计链表')

function removeNthFromEnd(head, n) {
    let dummyHead = new ListNode(0, head)
    let slow = dummyHead
    let fast = head
    while (n--) {
        fast = fast.next
    }
    while (fast) {
        slow = slow.next
        fast = fast.next
    }
    slow.next = slow.next.next
    return dummyHead.next
}

let list = new LinkedList([2, 5, 1, 7, 3, 9])
let res = removeNthFromEnd(list.head, 2)
console.log(res);